单调队列 模板+例题

概述

单调队列是一种维护队列的队列。它的思想是在决策集合中及时排除一定不是最优解的选择。时间复杂度 $O(N)$。

它是这么实现的：

1. 在队尾加入元素： 若加入该元素不能使队列单调，不断移除队尾元素。否则在队尾加入给定元素。
2. 队首元素出队： 如果队头元素在原队列中应当出队，就不断出队。

这样，单调队列始终保持单调性。这种性质可以用来求最值。

例题

LuoguP1886 滑动窗口 /【模板】单调队列

最基本的单调队列。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,k,a[N],up[N],down[N];
class que{
	int head,tail;
	bool ml;//true more, false less
	pair<int,int> node[1001];
	public:
		que(bool ml):ml(ml){head=1;tail=0;};
		bool cmp(int x,int y){
			if(ml)return x<y;
			else return x>y;
		}
		void pushback(int position,int data){
			while(head<=tail&&(!cmp(node[tail].second,data)))tail--;
			node[++tail]=make_pair(position,data);
		}
		void popfront(int position){
			if(node[head].first<=position)head++;
		}
		int top(){return node[head].second;}
};
signed main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	que upq(true),doq(false);
	for(int i=1;i<=n;i++){
		upq.pushback(i,a[i]);
		doq.pushback(i,a[i]);
		if(i<k)continue;
		up[i]=upq.top();
		down[i]=doq.top();
		upq.popfront(i-k+1);
		doq.popfront(i-k+1);
	}
	for(int i=k;i<=n;i++)printf("%d ",up[i]);
	putchar('\n');
	for(int i=k;i<=n;i++)printf("%d ",down[i]);
	return 0;
}

LuoguP2251 质量检测

上题的子问题。略。

LuoguP1714 切蛋糕

最大子段和问题。题解。